package Arrays;

public class _64_MinimumPathSum {
    //recursion solution
    //exceeded time limited
    public int minPathSum0(int[][] grid) {
        return getPath(grid, 0,0);
    }

    public int getPath(int[][] grid, int ver, int hor) {
        if (ver > grid.length - 1 || hor > grid[0].length - 1) {
            return Integer.MAX_VALUE;
        }
        if (ver == grid.length - 1 && hor == grid[0].length - 1) {
            return grid[ver][hor];
        }
        return grid[ver][hor] + Math.min(getPath(grid,ver,hor+1), getPath(grid,ver+1,hor));
    }

    //solution 2:using memory
    public int minPathSum(int[][] grid) {
        int[][] min = new int[grid.length][grid[0].length];
         getMinPaths(grid, min, 0, 0, 0);
        return min[grid.length-1][grid[0].length-1];
    }

    public void getMinPaths(int[][] grid, int[][] min, int ver, int hor,int prevSum) {
        if (ver > grid.length - 1 || hor > grid[0].length - 1) {
            return ;
        }
        if (min[ver][hor] == 0) {
            min[ver][hor] = prevSum + grid[ver][hor];
            getMinPaths(grid, min, ver, hor + 1, min[ver][hor]);
            getMinPaths(grid, min, ver + 1, hor, min[ver][hor]);
        } else {
            if (prevSum + grid[ver][hor] < min[ver][hor]) {
                min[ver][hor] = prevSum + grid[ver][hor];
                getMinPaths(grid, min, ver, hor + 1, min[ver][hor]);
                getMinPaths(grid, min, ver + 1, hor, min[ver][hor]);
            } else {
                return;
            }
        }
    }

    //reference solution:faster
    //hint:start from the end to the begin,and every sum only calculate once.
    public static int minPathSum1(int[][] grid) {
        /* sanity check */
        if ( grid == null) {
            return -1;
        }

        int row = grid.length;
        int col = grid[0].length;
        int sum[][] = new int[row][col];
        /* Base case */
        sum[row-1][col-1] = grid[row-1][col-1];
        minPathSumHelper(grid, row, col, 0, 0, sum);

        return sum[0][0];
    }
    private static int minPathSumHelper( int[][]grid, int row, int col,
                                         int curRow, int curCol, int[][]sum){

        if (sum[curRow][curCol] != 0) {
            return sum[curRow][curCol];
        }

        if (curRow == row-1 && curCol == col - 1) {
            return grid[curRow][curCol];
        }

        int leftPathSum = Integer.MAX_VALUE;
        int downPathSum = Integer.MAX_VALUE;
        //go down
        if ( curRow + 1 <= row - 1) {
            leftPathSum = minPathSumHelper(grid,row,col,curRow+1,curCol,sum);
        }
        //turn right
        if ( curCol + 1 <= col - 1) {
            downPathSum = minPathSumHelper(grid,row,col,curRow,curCol+1, sum);
        }
        sum[curRow][curCol] = Math.min(leftPathSum,downPathSum) + grid[curRow][curCol];
        return sum[curRow][curCol];
    }
}
